import java.util.List;

public class MinimumTotal {
    public static void main(String[] args) {

    }
    public int minimumTotal(List<List<Integer>> triangle) {
        //使用dp
        //状态数组
        //dp方程：f(i,j) = min(f(i+1,j),f(i+1,j+1))+a[i][j]
        int row = triangle.size();
        int column = triangle.get(row-1).size();
        int[] nums = new int[triangle.get(row-1).size()];
        for(int i=0;i<nums.length;i++){
            nums[i] = triangle.get(row-1).get(i);
        }
        for(int i =row-2;i>=0;i--){
            List<Integer> list = triangle.get(i);
            for(int j=0;j<list.size();j++){
                nums[j] = Math.min(nums[j],nums[j+1])+triangle.get(i).get(j);
            }
        }
        return nums[0];
    }
}
